#include<unordered_set>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        unordered_set<string> hashSet;
        for (auto str : dictionary) {
            hashSet.insert(str);
        }
        int size = sentence.length();
        int* dp = new int[size + 1];
        fill(dp, dp + size + 1, 0);
        for (int i = 1; i < size + 1; ++i) {
            dp[i] = dp[i - 1] + 1;
            for (int len = 1; len <= i; ++len) {
                if (hashSet.find(sentence.substr(i - len, len)) != hashSet.end()) {
                    dp[i] = min(dp[i], dp[i - len]);
                }
            }
        }
        int res = dp[size];
        delete[] dp;
        return res;
    }
};